package leetcode.d_300_plus;

import java.util.*;

public class P994 {
    public static void main(String[] args) {
        P994.Solution solution = new P994().new Solution();
        int[][] grid = new int[][]{
                {2,1,1},
                {1,1,0},
                {0,1,1}
        };
        System.out.println(solution.orangesRotting(grid));
    }

    public void add (Integer num) {
        num++;
    }

    class Solution {
        public int orangesRotting(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            Queue<int[]> queue = new LinkedList<>();
            int count = 0;

            for (int i=0; i<m; i++) {
                for (int j=0; j<n; j++) {
                    if (grid[i][j] == 1) {
                        count ++;
                    }
                    if (grid[i][j] == 2) {
                        queue.add(new int[]{i, j});
                    }
                }
            }

            int round = 0;
            while (count>0 && !queue.isEmpty()) {
                round++;
                int queueLen = queue.size();
                for (int k=0; k<queueLen; k++) {
                    int[] index =  queue.poll();
                    int i = index[0];
                    int j = index[1];
                    if (i-1>=0 && grid[i-1][j] == 1) {
                        grid[i-1][j] = 2;
                        count--;
                        queue.add(new int[]{i-1, j});
                    }
                    if (i+1<m && grid[i+1][j] == 1) {
                        grid[i+1][j] = 2;
                        count--;
                        queue.add(new int[]{i+1, j});
                    }
                    if (j-1>=0 && grid[i][j-1] == 1) {
                        grid[i][j-1] = 2;
                        count--;
                        queue.add(new int[]{i, j-1});
                    }
                    if (j+1<n && grid[i][j+1] == 1) {
                        grid[i][j+1] = 2;
                        count--;
                        queue.add(new int[]{i, j+1});
                    }
                }
            }

            if (count > 0) {
                return -1;
            }
            return round;
        }
    }
}
